package com.li.algorithm.leetcode.hot100;


public class Test26 {

    /**
     * 方法1：
     *  遍历链表，直到某个节点被访问两次
     *  将链表中的对象放到Map中
     *  时间复杂度：O(N)；空间复杂度：O(N)
     */
//    public ListNode detectCycle(ListNode head) {
//        ListNode p = head;
//        Set<ListNode> visited  = new HashSet<>();
//        visited.add(p);
//        while (p != null && p.next != null) {
//            p = p.next;
//            if (visited.contains(p)) {
//                return p;
//            }
//            visited.add(p);
//        }
//        return null;
//    }

    /**
     * 方法2：快慢指针——我们使用两个指针，fast 与 slow。它们起始都位于链表的头部。
     * 随后，slow 指针每次向后移动一个位置，而 fast 指针向后移动两个位置。
     * 如果链表中存在环，则 fast 指针最终将再次与 slow 指针在环中相遇。
     *
     * 假设链表的头节点到环入口的距离为a，环的长度为b。
     * 当fast和slow第一次相遇时，fast走过的距离是slow的两倍。
     * 设slow走的距离为x，则fast走的距离为2x。
     *
     * fast比slow多走了n圈环:
     * 2x = x + n*b
     * 得到相遇时slow走的距离是环长的整数倍：
     * x = n*b
     *
     * 如果slow从起点重新回到环入口，则需要走：
     * l = a + n*b
     *
     * 故slow和fast相遇点到环入口的距离为a
     * 此时放一个指针到head位置出发，经过a距离后可以和slow在环入口相遇
     *
     * 时间复杂度：O(N)；空间复杂度：O(1)
     */
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null) {
            slow = slow.next;
            if (fast.next != null) {
                fast = fast.next.next;
            } else {
                return null;
            }
            if (slow == fast) {
                ListNode temp = head;
                while (temp != slow) {
                    temp = temp.next;
                    slow = slow.next;
                }
                return temp;
            }
        }
        return null;
    }
}
